public class test {
    //leetcode 673.最长递增子序列个数
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            // 1. 创建dp表
            int n = nums.length;
            // dp[i]代表以i结束时,最长递增子序列的长度
            int[] dp = new int[n];
            // cnt[i]代表以i结束时,最长递增子序列的个数
            int[] cnt = new int[n];
            int maxlen = 0;
            int max = 0;
            // 2. 初始化
            Arrays.fill(dp, 1);
            Arrays.fill(cnt, 1);
            // 3. 填表
            for (int i = 0; i < n; i++) {
                for (int j = i; j >= 0; j--) {
                    // 只有此时的nums[i] > nums[j],才能组成递增子序列
                    if (nums[i] > nums[j]) {
                        if (dp[j] + 1 > dp[i]) {
                            // 个数更新
                            // 相当于在cnt[j]中的子序列后都加一个nums[i]
                            // 故直接变成cnt[j]的个数
                            dp[i] = dp[j] + 1;
                            cnt[i] = cnt[j];
                        } else if (dp[j] + 1 == dp[i]) {
                            cnt[i] += cnt[j];
                        }
                    }
                }
                if (dp[i] > maxlen) {
                    maxlen = dp[i];
                    // 更新为新长度子序列的个数
                    max = cnt[i];
                } else if (dp[i] == maxlen) {
                    max += cnt[i];
                }
            }
            // 4. 返回值
            return max;
        }
    }
    //leetcode 646.最长数对链
    class Solution {
        public int findLongestChain(int[][] pairs) {
            // 1. 创建dp[]表
            int n = pairs.length;
            int[] dp = new int[n];
            // 2. 初始化
            // 按照pairs[i][0]升序排列
            Arrays.sort(pairs,(a,b) -> a[0] - b[0]);
            Arrays.fill(dp,1);
            // 3. 填表
            for(int i = 0;i < n;i++){
                for(int j = i;j >= 0;j--){
                    if(pairs[i][0] > pairs[j][1]){
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }
                }
            }
            // 4. 返回值
            return dp[n - 1];
        }
    }
    //leetcode 1218.最长定差子序列
    class Solution {
        public int longestSubsequence(int[] arr, int difference) {
            // 1. 创建dp表
            HashMap<Integer,Integer> map = new HashMap<>();
            int num = 0;
            int n = arr.length;
            // 2. 初始化

            // 3. 填表
            for(int i = 0;i < n;i++){
                map.put(arr[i],map.getOrDefault(arr[i] - difference,0) + 1);
                num = Math.max(map.get(arr[i]),num);
            }
            // 4. 返回值
            return num;
        }
    }
    //leetcode 1027.最长等差数列
    class Solution {
        public int longestArithSeqLength(int[] nums) {
            // 1. 创建dp表
            //key为nums的值,values为对应的下标
            HashMap<Integer,Integer> map = new HashMap<>();
            int n = nums.length;
            if(n <= 2){
                return n;
            }
            //代表以[i][j]为结尾的最长等差数列的长度
            int[][] dp = new int[n][n];
            int max = 2;
            // 2. 初始化
            for(int i = 0;i < n;i++){
                Arrays.fill(dp[i],2);
            }
            // 3. 填表
            for(int i = 0;i < n;i++){
                for(int j = i + 1;j < n;j++){
                    //当前两个元素的公差
                    int diff = nums[j] - nums[i];
                    int prev = nums[i] - diff;
                    int index = map.getOrDefault(nums[i] - diff,-1);
                    if(index >= 0){
                        dp[i][j] = dp[index][i] + 1;
                        max = Math.max(max,dp[i][j]);
                    }
                }
                map.put(nums[i],i);
            }
            // 4. 返回值
            return max;
        }
    }
}
